class Solution
{
public:
    long long minCost(vector<int> &nums, vector<int> &cost)
    {
        int n = nums.size();
        vector<array<long long, 2>> numCostPair(n);
        for (int i = 0; i < n; ++i)
        {
            numCostPair[i] = {nums[i], cost[i]};
        }
        sort(numCostPair.begin(), numCostPair.end());
        vector<long long> costPrefixSum(n);
        costPrefixSum[0] = numCostPair[0][1];
        for (int i = 1; i < n; ++i)
        {
            costPrefixSum[i] = costPrefixSum[i - 1] + numCostPair[i][1];
        }
        long long totalCost = 0;
        // 可以证明最小值点一定在nums中的元素上取到，于是遍历每一个点的totalCost
        for (int i = 1; i < n; ++i) // 求全部变成最小值的cost
        {
            totalCost += (numCostPair[i][0] - numCostPair[0][0]) * numCostPair[i][1];
        }
        long long minTotalCost = totalCost;
        for (int i = 1; i < n; ++i)
        {
            long long step = numCostPair[i][0] - numCostPair[i - 1][0];
            // totalCost += costPrefixSum[i - 1] * step - (costPrefixSum[n - 1] - costPrefixSum[i - 1]) * step;
            totalCost -= step * (costPrefixSum[n - 1] - (costPrefixSum[i - 1] << 1)); // 简化了一下表达式
            minTotalCost = min(minTotalCost, totalCost);                              // 理论上totalCost第一次上升就可以停止遍历了
        }
        return minTotalCost;
    }
};